#define _CRT_SECURE_NO_WARNINGS 1


struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(nullptr), right(nullptr) {
	}
};

class Solution {
public:
	void _convert(TreeNode* root, TreeNode*& prev)
	{
		if (root == nullptr)
			return;
		_convert(root->left, prev);
		if (prev)
			prev->right = root;
		root->left = prev;
		prev = root;
		_convert(root->right, prev);
	}

	TreeNode* Convert(TreeNode* pRootOfTree) {
		if (pRootOfTree == nullptr)
			return nullptr;
		TreeNode* p = nullptr;
		_convert(pRootOfTree, p);
		TreeNode* pcur = pRootOfTree;
		while (pcur->left)
		{
			pcur = pcur->left;
		}
		return pcur;
	}
};
